package com.example.jianbing.DataStructures.sort;

import org.apache.catalina.valves.rewrite.InternalRewriteMap;

import java.lang.annotation.ElementType;
import java.util.concurrent.ForkJoinPool;

/**
 * @ClassName : SortDemo
 * @Description : 排序算法
 * @Author : JB
 * @Date: 2020-12-06 20:06
 */


public class SortDemo {



    /**
     * 直接插入排序
     * @param arr
     */
    public static int[]  insertSort(int[] arr){
         int x ,i,j;
         for ( i = 1; i < arr.length; i++) {
             if (arr[i] < arr[i - 1]) {
                 x = arr[i];
                for ( j = i - 1; j >= 0 && x < arr[j]; --j) {
                    arr[j + 1] = arr[j];
                }
                arr[j+1] = x;
            }
         }
        return arr;
    }

    /***
     * 折半插入排序
     * @param arr
     * @return
     */
    public static int[] insertSortV2(int[] arr){

        int x,i,j,low,hign,mid;
        for ( i = 1; i < arr.length  ; i++) {
            if(arr[i] < arr[i-1]){
                x = arr[i];
                low = 0;hign = i-1;  //采用二分查找法查找插入的位置
                while (low<=hign){
                    mid = (low+hign)/2;
                    if(arr[mid] < x){
                        low = mid+1;
                    }else{
                        hign = mid-1;
                    }
                }//循环结束，hign+1为插入的位置
                for (j = i-1;j >=hign+1;--j ){  //移动元素
                    arr[j+1] = arr[j];
                }
                arr[hign+1] = x;
            }
        }
        return  arr;
    }

    /***
     * 希尔排序
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr){
        int len = arr.length;
        int temp,gap = len/2;
        while(gap >0){
            for(int i = gap; i < len;i++){
                if(arr[i] < arr[i-gap]){
                    temp = arr[i];
                    int j = i -gap;
                    while (j >=0 &&  arr[j] > temp){
                        arr[j+gap] = arr[j];
                        j = j -gap;
                    }
                    arr[j+gap] = temp;
                }
            }
            gap  = gap /2;
        }
        return  arr;
    }

    public static void   quickSort(int[] arr,int start,int end){
        int pivo ;
       if(start < end){
            pivo = partition(arr,start,end);
            quickSort(arr,start,pivo-1);
            quickSort(arr,pivo+1,end);
       }

    }
    public static int partition(int[] arr, int start, int end) {
        int pro = arr[start];
        while (start < end){
            while (start < end && arr[end] >= pro )  --end;
            arr[start] = arr[end];
            while ((start < end && arr[start] <= pro)) ++start;
            arr[end] = arr[start];
        }
        arr[start]  = pro;
        return start;
    }




    public static void main(String[] args) {
        int i;
        //int arr[] = {5,6,8,2,6,1,6,32,4};
        int arr[] = {1,5,4,4,2,1,9};
        //insertSort(arr);
        //insertSortV2(arr);
        //shellSort(arr);
        quickSort(arr,0,arr.length-1);
        for ( i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
